﻿#region

using System.Collections.Generic;

#endregion

namespace Domain.Algorithms {
    public static class Kruskal {
        public static Graph<Edge> FindSpaningTree(Graph<Edge> graph) {
            var edges = graph.Edges;
            edges.Sort(new WeigthEdgeSorterDescending());

            var treeId = new Dictionary<Vertex, int>();

            foreach (var vertex in graph.Vertices) {
                treeId[vertex] = vertex.Id;
            }

            var spanningTree = new Graph<Edge>(graph.Vertices);

            for (var i = 0; i < edges.Count; ++i) {
                var a = edges[i].VertexStart;
                var b = edges[i].VertexEnd;
                var l = edges[i].Weight;
                if (treeId[a] != treeId[b]) {
                    spanningTree.AddEdge(edges[i]);
                    var oldId = treeId[b];
                    var newId = treeId[a];
                    foreach (var vertex in graph.Vertices) {
                        if (treeId[vertex] == oldId)
                            treeId[vertex] = newId;
                    }
                }
            }

            return spanningTree;
        }
    }
}